// 267.[没做] 回文排列 II
// https://leetcode.cn/problemset/all/?search=267&page=1
// https://www.cnblogs.com/grandyang/p/5315227.html
// https://blog.csdn.net/qq_33185750/article/details/108093916
// [LeetCode] 267. Palindrome Permutation II 回文全排列之二
// Given a string s, return all the palindromic permutations (without
// duplicates) of it. Return an empty list if no palindromic permutation could
// be form. Example 1:"aabb"
// ["abba", "baab"]
// Example 2:"abc"
// []
// Hint: If a palindromic permutation exists, we just need to generate the first
// half of the string. To generate all distinct permutations of a (half of)
// string, use a similar approach from: Permutations II or Next Permutation.
// 这道题是之前那道 Palindrome Permutation
// 的拓展，那道题只是让判断存不存在回文全排列，
// 而这题让返回所有的回文全排列，此题给了我们充分的提示：如果回文全排列存在，
// 只需要生成前半段字符串即可，后面的直接根据前半段得到。那么再进一步思考，
// 由于回文字符串有奇偶两种情况，偶数回文串例如 abba，可以平均分成前后半段，
// 而奇数回文串例如
// abcba，需要分成前中后三段，需要注意的是中间部分只能是一个字符，
// 可以分析得出，如果一个字符串的回文字符串要存在，那么奇数个的字符只能有0个或1个，
// 其余的必须是偶数个，所以可以用哈希表来记录所有字符的出现个数，然后找出出现奇数次数的字符加入
// mid 中，
// 如果有两个或两个以上的奇数个数的字符，则返回空集，对于每个字符，不管其奇偶，
// 都将其个数除以2的个数的字符加入t中，这样做的原因是如果是偶数个，将其一般加入t中，
// 如果是奇数，如果有1个，除以2是0，不会有字符加入t，如果是3个，除以2是1，取一个加入t。
// 等获得了t之后，t是就是前半段字符，对其做全排列，每得到一个全排列，
// 加上 mid
// 和该全排列的逆序列就是一种所求的回文字符串，这样就可以得到所有的回文全排列了。
// 在全排序的子函数中有一点需要注意的是，如果直接用数组来保存结果时，
// 并且t中如果有重复字符的话可能会出现重复项，比如 t = "baa"
// 的话，那么最终生成的结果会有重复项，
// 不信可以自己尝试一下。这里简单的说明一下，当 start=0，i=1 时，交换后得到
// aba， 在之后当 start=1，i=2 时，交换后可以得到
// aab。但是在之后回到第一层当baa后， 当 start=0，i=2 时，交换后又得到了
// aab，重复就产生了。那么其实最简单当去重复的方法 就是将结果 res 定义成
// HashSet，利用其去重复的特性，可以保证得到的是没有重复的，参见代码如下：
// 解法一：
// 下面这种方法和上面的方法很相似，不同之处来于求全排列的方法略有不同，
// 上面那种方法是通过交换字符的位置来生成不同的字符串，而下面这种方法
// 是通过加不同的字符来生成全排列字符串，参见代码如下：
// 解法二：
// 在来看一种利用了 std 提供的 next_permutation
// 函数来实现的方法，这样就大大减轻了我们的工作量，
// 但是这种方法个人感觉算是有些投机取巧了，不知道面试的时候面试官允不允许这样做，
// 贴上来拓宽一下思路也是好的：解法三：
// Github 同步地址：https://github.com/grandyang/leetcode/issues/267
